/* 
   Arassaja experimental,
   (C) Copyright Atamyrat Hezretguliyev, 2006
   http://www.tmolympiad.org/
   atamyrat@gmail.com
   
   License: GNU GPL v2
   SVN test 2
*/
#ifndef __ARASSAJA_H__
#define __ARASSAJA_H__


#include<iostream>
#include<fstream>
#include<string>
#include<vector>
using namespace std;


#define DEFAULT_HMM_FILE "hmm.txt"

const double EPS = 0.000000000000001;
const int MAXN = 6000;
const int MAXBOGUN = 40;

int n;
vector<string> bgs;
vector<int> bg_count;

double pi[MAXN];
double a[MAXN][MAXN];

/* bogun berilyar, sonin ID-sini return et */
int find_bogun(string bg)
{
	for(int i=0; i<bgs.size(); i++)
		if( bgs[i] == bg ) return i;
	return -99;
}

/* decode: internal encodingden UTF8 convert et */
string tk2u(string a) {
    string ret = "";
    int len = a.length();
    for(int i=0; i<len; i++) {
      switch( a[i] ) {
          case '1': ret=ret+char(0xc3)+char(0x87); break;
          case '2': ret=ret+char(0xc3)+char(0x84); break;
          case '3': ret=ret+char(0xc3)+char(0x96); break;
          case '4': ret=ret+char(0xc3)+char(0x9c); break;
          case '5': ret=ret+char(0xc3)+char(0x9d); break;
          case '6': ret=ret+char(0xc3)+char(0xa7); break;
          case '7': ret=ret+char(0xc3)+char(0xa4); break;
          case '8': ret=ret+char(0xc3)+char(0xb6); break;
          case '9': ret=ret+char(0xc3)+char(0xbc); break;
          case '0': ret=ret+char(0xc3)+char(0xbd); break;
          case '!': ret=ret+char(0xc5)+char(0xbe); break;
          case '@': ret=ret+char(0xc5)+char(0x88); break;
          case '#': ret=ret+char(0xc5)+char(0x9e); break;
          case '$': ret=ret+char(0xc5)+char(0x9f); break;
          case '%': ret=ret+char(0xc5)+char(0xbd); break;
          case '^': ret=ret+char(0xc5)+char(0x87); break;
          default:
              ret=ret+a[i];
      }
    }
    return ret;
}

/* UTF8-den internal encodinge convert et */
string u2tk(string a) {
    
    // initialize one-to-one mapping
    char map1[256];
    for(int i=0; i<256; i++) map1[i] = i;
    
    /* 2 byte - to - 1 byte mapping */
    int twobyte[256];

    memset(twobyte, 0, sizeof(twobyte));
    twobyte[0xC3] = 1;
    twobyte[0xC5] = 2;
    
    char map2[3][256];
    memset(map2, 0, sizeof(map2));
    
    map2[1][ 0x87 ] = '1';
    map2[1][ 0x84 ] = '2';
    map2[1][ 0x96 ] = '3';
    map2[1][ 0x9C ] = '4';
    map2[1][ 0x9D ] = '5';
    map2[1][ 0xA7 ] = '6';
    map2[1][ 0xA4 ] = '7';
    map2[1][ 0xB6 ] = '8';
    map2[1][ 0xBC ] = '9';
    map2[1][ 0xBD ] = '0';    
    map2[2][ 0xBE ] = '!';
    map2[2][ 0x88 ] = '@';
    map2[2][ 0x9E ] = '#';
    map2[2][ 0x9F ] = '$';
    map2[2][ 0xBD ] = '%';
    map2[2][ 0x87 ] = '^';
        
    int len = a.length();    
    string ret;
    int aa,bb = 0;
    
    for(int i=0; i<len; i++) {
        
        aa = (unsigned char)(a[i]);
        bb = 0;
        if(i+1 < len ) bb = (unsigned char)(a[i+1]);
        
        if( aa == 0xE2 && bb == 0x84) {
                if(i+2<len) {
                    if(int(a[i+2])+128 == 0x96) {
                       /* 0xE28496 => '`'; */
                        ret = ret + '`';
                        i+=2;
                        continue;
                    }
                }
        }
        
        
        if( twobyte[ aa ] ) {
            if( map2[ twobyte[ aa ] ][ bb ] ) {
                ret = ret + ( map2[ twobyte[ aa ] ][ bb ] );
                i++;
                continue;
            }
        }
        
        ret = ret + ( map1[ aa ] );
    }
    return ret;
}

/* in-den target yasalmasy mumkinmi? */
bool possible(string in, string target)
{
	if( in.length() != target.length() ) return 0;
	for(int i=0; i<in.length(); i++) {
		char s = in[i];
		char t = target[i];
		if(s==t) continue;
		if(s=='c' && t=='6') continue;
		if(s=='a' && t=='7') continue;
		if(s=='o' && t=='8') continue;
		if(s=='u' && t=='9') continue;
		if(s=='n' && t=='@') continue;
		if(s=='i' && t=='y') continue;
		if(s=='s' && t=='$') continue;
		if(s=='z' && t=='!') continue;
		return false;
	}
	return true;
}

/* cekimli: c- cekimlimi yada dal soni barla */
bool cekimli(char c) {
     if(c=='a') return 1;
     if(c=='e') return 1;
     if(c=='y') return 1;
     if(c=='u') return 1;
     if(c=='i') return 1;
     if(c=='o') return 1;
     if(c=='7') return 1;
     if(c=='8') return 1;
     if(c=='9') return 1; 
     return 0;
}

/* str berilyar. sony bogunlara bol we vector return et */
vector<string> boguna_bol(string str) {
       vector<string> bogunlar;
       string bogun = "";
       bool cekimlibar = false;
       for(int i=str.length()-1; i>=0; i--) {
               bogun=str[i]+bogun;
               if( cekimli(str[i]) ) {
                   cekimlibar = true;                   
               } else
               if( cekimlibar ) {
                   bogunlar.push_back(bogun);
                   bogun = "";
                   cekimlibar = false;
               }
       }
       if(bogun!="") bogunlar.push_back(bogun);
       reverse(bogunlar.begin(), bogunlar.end());       
       return bogunlar;
}

/* Hidden Markov Model fayldan oka */
void load_hmm_file()
{
	ifstream fin(DEFAULT_HMM_FILE);
	n=0;
	memset(pi,0,sizeof(pi));
	memset(a, 0, sizeof(a));
	bgs.empty();

	string bogun;
	double ps;
	int i = 0;
	while( fin >> bogun >> ps ) {
		bgs.push_back(bogun);
		pi[i] = ps;
		int j;
		while((fin >> j) && j!=-1 ) 
			fin >> a[i][j];
		i++;
	}
	n=i;
}

// i-den sonra j gelip bilermi? owrenen zatlarymda yok, so guessing...
bool likely(int i, int j)
{
	string ii = bgs[i];
	string jj = bgs[j];
	char c1='e', c2='e';
	for(int k=ii.length()-1; k>=0; k--)
		if( cekimli(ii[k]) ) {
			c1 = ii[k]; break;
		}
	for(int k=jj.length()-1; k>=0; k--)
		if( cekimli(jj[k]) ) {
			c2 = jj[k]; break;
		}
	if( c1=='a' || c1=='o' || c1=='u' || c1=='y') c1='1'; else c1='0';
	if( c2=='a' || c2=='o' || c2=='u' || c2=='y') c2='1'; else c2='0';
	
	if( c1==c2 ) return true;
	return false;
}


int nbogun;
int subst[MAXBOGUN][10];
int deg[MAXBOGUN];

int nvs = 0;
double prs[100];
string vs[100];

// Viterbi yazmaga yaltanyan we gerek hem dal... forward algoritm yeterlay su wagtlykca...
void go(int step=0, double pr=10000, string v="", int prev=0)
{
	//cout << "go " << step << " " << pr << " " << v << endl;
	if( pr<EPS ) return;

	if( step==nbogun ) {
		//cout << tk2u(v) << " " << pr << endl;
		vs[nvs] = v;
		prs[nvs] = pr;
		nvs++;		
		return;
	}
	bool stuk = true;
	for(int i=0; i<deg[step]; i++) {
		double pr2 = pr;
		if(step==0) 
			pr2*=pi[ subst[step][i] ];
		else
			pr2*=a[prev][ subst[step][i] ];

		if( pr2<EPS ) continue;

		stuk = false;

		go(step+1, pr2, v+bgs[subst[step][i]], subst[step][i] );
	}

	// cikmaz yola girdik. go to most likely branch
	if( stuk && step>=2) {
		//cout << "guessing... at step " << step << endl;
		for(int i=0; i<deg[step]; i++) {
			if( step>0 && !likely(prev, subst[step][i] ) ) continue;
			go(step+1, pr, v+bgs[subst[step][i]], subst[step][i] );
		}
	}
}

/* string berilyar. soni hemmesini kici harplara owur */
string lower(string tmp) {
       for(int i=0; i<tmp.length(); i++) {
               char c = tmp[i];
               if( isupper(c) ) c = tolower(c);

               if( c=='1' ) c='6';
               if( c=='2' ) c='7';
               if( c=='3' ) c='8';
               if( c=='4' ) c='9';
               if( c=='5' ) c='0';
               if( c=='%' ) c='!';
               if( c=='^' ) c='@';
               if( c=='#' ) c='$';


               tmp[i] = c;
       }
       return tmp;
}

/* berilen harp ulymy? (BELLIK: internal encoding bilen isleyar) */
bool isupper2(char c)
{
     if( isupper(c) ) return true;
     if( '1'<=c && c<='5' ) return true;
     if( c=='%' || c=='^' || c=='#') return true;
     return false;
}

/* bizin encodingde bir harpy ula owur */
char toupper2(char c) 
{
     if( islower(c) ) return toupper(c);
   if( c=='6' ) c='1';
   if( c=='7' ) c='2';
   if( c=='8' ) c='3';
   if( c=='9' ) c='4';
   if( c=='0' ) c='5';
   if( c=='!' ) c='%';
   if( c=='@' ) c='^';
   if( c=='$' ) c='#';
     return c;
}

/* 100% belli we dogry isleyan kanunlari islet */
string obvious(string wrd)
{
	string ret = "";
	for(int i=0; i<wrd.size(); i++) {
		char c = wrd[i];
		
		if(c=='c') c='6';
		if(c=='y') {
			if( i && cekimli(wrd[i-1])) c='0';
			if( i<wrd.size()-1 && cekimli(wrd[i+1])) c='0';
		}
		ret+=c;
	}
	return ret;
}

/* 
 * no comments...
 */
bool uppers[40];
void save_case_info(string s)
{
     for(int i=0; i<s.length(); i++)
             uppers[i] = isupper2(s[i]);
}
string apply_cases(string &s)
{
     for(int i=0; i<s.length(); i++)
             if( uppers[i] )
                 s[i] = toupper2(s[i]);
     return s;
}

vector<string> suggest(string inp)
{
     save_case_info(inp);
	string word = obvious(lower(inp));

	vector<string> bogunlar = boguna_bol(word);
	memset(deg,0,sizeof(deg));
	nbogun = bogunlar.size();
	
	for(int i=0; i<nbogun; i++) {
		//cout << bogunlar[i] << endl;
		for(int j=0; j<n; j++)
			if( possible(bogunlar[i], bgs[j]) ) {
				//cout << "  -> " << tk2u(bgs[j]) << endl;
				subst[i][deg[i]++] = j;
			}
	}

	nvs = 0;
	go(0);

	double ttl=0;
	for(int i=0; i<nvs; i++) {
        	for(int j=i+1; j<nvs; j++)
		if( prs[i] < prs[j] ) {
			double tmp = prs[i];
			prs[i] = prs[j];
			prs[j] = tmp;
			string tmpv = vs[i];
			vs[i] = vs[j];
			vs[j] = tmpv;
		}
		ttl+=prs[i];
	}

  vector<string> sugs;
	for(int i=0; i<nvs; i++) 
		sugs.push_back(tk2u(apply_cases(vs[i])));
  reverse(sugs.begin(), sugs.end());
  
   return sugs;
}

int test_arassaja(int argc, char *argv[])
{
	cout << "@(#) Arassaja beta version 0.7 http://www.tmolympiad.org/" << endl;

	load_hmm_file();

	while(2) {
		string word = "!";
		cin >> word;
		if(cin.bad() || cin.eof()) return 0;

        vector<string> sgs;

		sgs = suggest(word);
		for(int i=0; i<sgs.size(); i++)
		        cout << sgs[i] << endl;
		cout << endl;
	}
	return 0;
}



#endif
